\chapter{Two-Stage Capacity Expansion in Survivable Networks}

\label{chap-two}





Network capacity expansion under uncertainty is an important class of problems
arising in many contexts including transportation and telecommunication networks. 
This problem has been the center of attention in the context of transportation
 networks due to increasing need for natural disaster preparedness.
 Transportation network components are usually vulnerable to large 
 scale urban hazards such as earthquakes, hurricanes and floods.
 For example the 1994 Northridge earthquake caused damage to 286 state highway
 bridges, out of which seven major ones collapsed \cite{Liu:2009:TSP:1460926.1461006}.
  A damaged transportation network not only affects the normal functionality of modern societies, 
  but also directly impacts the effectiveness of post-disaster rescue and recovery activities. 
  The importance of unimpeded operation of transportation networks raises the question of how to
   optimally allocate resources for installing additional capacities to the network components to
    improve the robustness of the entire network.


\section{Problem Statement}
Network capacity expansion problems are central to a large number of contexts
including transportation, distribution and telecommunication. The idea is to
expand a network of links (roads, electric lines, transportation means. etc.) to
enable the flow of commodities (people, data, material, etc.) in order to
satisfy some demands.
However, in many practical applications a resilience dimension should be added
to designing  and expanding such networks.This set of network optimization problems is studied not only
 under the normal operating state, but also under a set of states corresponding to a selected set of
  possible failure situations.
\\
Applications of this class of problems can be found in many critical
infrastructures that are vulnerable to large scale urban disasters, such as earthquakes, hurricanes 
and flood. As the smooth operation of such infrastructures is important, preventive measures
 should be taken to minimize the possibility of service outage.  
 One of these preventive measures that decision makers can take is to install 
 additional capacities on links to guarantee satisfying the demands under a set of possible
  failure situations. The different failure situations are characterized by the availability
   status of the links as well as demands for each situation. The issue is that the resulting
    network (after capacity expansion decisions are implemented) should be resilient to failures,
     i.e., the network should be able to satisfy the demands even when a part of the network is failed or degraded.
\\
The decision regarding the capacity expansions should be made with respect to
 the individual components and also the overall importance of the component to
 the performance of the whole infrastructure. This is because individual components
  in an infrastructure are not independent of each other. Any change in one component
   of the infrastructure may cause the flow of commodities to be re-distributed and
    therefore other components may be affected remotely.  Therefore decisions should be
     made at the infrastructure level.  The whole infrastructure maybe modeled as a network,
      and the components can be represented by network links. As the decision makers are trying 
      to protect the infrastructure, represented by a network against a set of possible failure states
      , the problem is often referred to as survivable network design and capacity expansion problems.
      In this class of problems decision makers are mostly interested in a set of capacity expansion 
      decisions for links that allows satisfying the demands while minimizing the cost. 


In the literature it is commonly assumed that demands between origin-destination node pairs are known when planning for capacity expansions in the networks; however, when operating under hazardous conditions, this assumption may not apply. Rather, the node-to-node demands are based on the hazardous conditions the network faces and their consequences. This means that the decisions for capacity expansions cannot be based only on the demands under normal conditions. The amount of demand between each origin-destination node pair vary under different hazardous conditions. We call each of these conditions a failure scenario.



Commonly transportation network components(e.g. road segments and bridges)are vulnerable to natural hazards, causing them to not behave as they do under normal condition. Therefore under each failure scenario each link in the network maybe completely failed or only partially available. The only information available to the decision maker at the time of planning for network capacity expansions is the fractional availability of each link under each failure scenario.


\subsection{Components of the problem}

\begin{enumerate}
  \item The Network \\ We assume we have a network $G =(V,E)$ where \textit{V}
  is the set of nodes and \textit{E} is the set of links (edges). Associated with each edge $e$ we have a capacity of $u_{e}$.
  We also have a demand matrix $ D =(d_{i,j})$ where $ d_{i,j} $  represents the
  demand that must be supplied to node $j$ from node $i$. We assume that under
  normal condition the link capacities are sufficient enough to allow the flow
  of material through the network to satisfy all demand.
  \item Failure Scenarios \\  We assume that the network described above is
  subject to various potentional failures. A network failure could potentially
  result in a change (reduction) in the capacity of each link as well as a
  change in demand $d_{i,j}$ between each pair of nodes $i$ and $j$. More
  specifically, we assume that associated with each scenario $s$ and for each
  edge $e \in E $ we have an associated value $\lambda_{e,s}$ that represents a
  fraction of the capacity of this edge that remains available if failure
  scenario $s$ occurs. Naturally $ 0 \leq $$\lambda_{e,s}$$\leq 1 $. We further
  assume that for each scenario $s$ we have a demand coefficient matrix
  $\mu_{s}=(\mu_{i,j,s})$ such that if failure scenario $s$ occurs the demand
  that must be supplied to node $j$ from $i$ changes to $\mu_{i,j,s} * d_{i,j}$.
  We assume $\mu_{i,j} \geq 0$; in other words  we assume that failure scenario
  $s$ could result in a reduction $(\mu_{i,j}<1)$ or an increase $(\mu_{i,j}>1)$
  in the demand from node $i$ to node $j$, or the demand could remain the same
  $(\mu_{i,j}=1)$.
  \item Decisions \\We assume that for each edge $e \in E $ have a set of
  expansion alternatives $L_{e}$, and for each alternative $l \in L_{e} $ we
  have a value $u_{e,l}$ that represents the increase in the capacity of edge
  $e$ if this alternative is selected, with an associated cost $c_{e,l}$. To
  simplify notation we use the notation $u_{e,0}$ to represent the original
  capacity of edge $e$ in this context. Hence if we choose to expand the
  capacity of edge $e$ according to alternative $l$, its capacity becomes
  $u_{e,0}+u_{e,l}$. The decision in this context is to select an expansion
  value for each edge $e$ in the network (i.e., an expansion plan)
  \end{enumerate}
  \subsection {Statement of the problem}
  Given 
  \begin {enumerate}
    \item Network $G =(V,E)$
    \item A capacity of $u_{e,0}$ associated with each edge $e \in E $
    \item A demand matrix $ D =(d_{i,j})$
    \item A set of failure scenarios $s=1$ to $S$, with the parameters
    $\lambda_{e,s}$, for all $e \in E$ and $\mu_{i,j,s}$, for all $i$ and $j$
    $\in V$
    \item A collection of expansion alternatives $L_{e}$ for each $e \in E$ and
    an expansion value $u_{e,l}$ and an expansion cost $c_{e,l}$ for each $l
    \in L_{e}$
  
  \end{enumerate}
  \hspace{8mm} We seek to answer the following two questions:
  \begin {enumerate}
    \item Is there an expansion plan for the network so that it remains feasible
    under every failure scenario?
    \item If the answer to the first question is yes, then find an expansion
    plan that would minimize the total expansion cost.
    \end{enumerate}




 %This chapter presents a modeling and solution approach for the problem of
 % capacity expansion of a minimum cost, survivable network. 
 %The concept of \textit{survivable} refers to the assumption that the network
 % is able to satisfy the demands under all the failure scenarios and fails under none of them. 
 %Therefore in this class of optimization problems, it is assumed that a network
 % should not only operate under the normal conditions, but also operate as expected under a finite set of failure scenarios. 



\section{Modeling Approach}



The proposed modeling approach is general and in principle can be
used to address capacity expansion decisions in survivable networks for any
type of networks, including telecommunication, computer, distribution and 
transportation networks. The goal of the problem is to identify the minimum cost 
capacity expansion plan that can satisfy the demands under all failure
scenarios.
Capacity expansion decisions need to be made before any failure scenario occurs,
 while a second set of decisions need to be made after information about the occurrence
  of a failure scenario is revealed. The second set of decisions would identify how to
  route flows on network paths based on the demands and available capacities under
  a failure scenario. This decision making structure suggests a framework for a two-stage
  decision making model, which only includes a first stage cost
 function (capacity expansion investments). 
  The second stage cost (recourse cost) is zero, 
  implying that no cost is incurred for routing the flows in the networks
  once enough capacity is available. As all the demands under all failure
  scenarios must be met, the probability distribution of the occurrence of the
   scenarios is not required; however more general versions of the problem can 
   account for failure probabilities and penalties for unmet demands, when
   unmet demands are allowed ( non-survivable models, with a penalty element
   for unsatisfied demands).


\begin{figure}

\centering

\includegraphics[width=0.6\textwidth]{Chapter-2/figs/decision}

\caption{Decision Making Flow}

\label{fig:hist2}

\end{figure}

\subsection{Modeling Assumptions}



%The network is modeled as a connected directed graph $G =(V,E)$ 
%where \textit{V} is the set of nodes and \textit{E} is the set of network
% links.
 %Point-to-point demands are to be routed in the network under a finite set of
 % possible failure scenarios.
 %The proposed modeling approach incorporates uncertainty in both availability
 % of capacities on links and origin destination pairs demands. 
 
 In the literature it is often assumed that links face
  a binary damage state (failed or undamaged); however our proposed modeling approach provides the opportunity
   for modeling partial failures (capacity loss)in any combination of links.


%The initial existing capacity on link $ e\in E$ is denoted by $U_{e,0}$.
 %As it is assumed there is a finite set of capacity expansion alternatives for
 % each link.
 Capacity expansion decision for each is represented by a set of binary variables with 1 
 representing that the alternative is chosen for the link and 0 otherwise. 
 The use of binary variables for capacity expansion decisions is because in most 
 applications it is required that links are of a modular capacity or there are only
  specific technological options available to be installed on each link , 
  and having any continuous value for links capacities is simply infeasible. 
  Rather, there are limited number of technological alternatives available to be installed for each link.
   %The capacity and cost associated with alternative \textit{i} for link
   % \textit{e} are denoted by $U_{e,i}$ and $C_{e,i}$ , respectively.



\begin{figure}

\centering

\includegraphics[width=0.4\textwidth]{Chapter-2/figs/network1}

\caption{Introductory Example Network}

\label{fig:hist1}

\end{figure}

\paragraph{Introductory Example}To motivate the problem, we start with a simple example. 
Consider the network in \fref{fig:hist1} with nodes $V=\left\{a,b,c,d\right\}$ and links
 $E=\left\{e\textit{1},e\textit{2},e\textit{3},e\textit{4},e\textit{5}\right\}$. 
 Suppose at any time the network is in either one of these two conditions: 
 the normal condition ($s_{0}$) under which the point-to-point travel demands 
 and link capacities are at their normal level; and a failed scenario ($s_{1}$) 
 under which the demands and available capacities of links vary from normal. 
 Tables \ref{tab:one} and \ref{tab:two} represent the network data under the two scenarios. 
 It can be easily computed that the network is not able to satisfy any of 
  the point-to-point demands under \textit{s1} scenario with the current available capacities.
   Therefore links capacities must be expanded to meet the demands under both scenarios.
    We have a set of capacity expansion alternatives that can be installed one at a time on each link,
     providing a set of mutually exclusive investment choices for each link represented by binary
      decision variables \textit{z}. The sample data regarding these capacity expansion alternatives
       and their associated costs are presented in Tables \ref{tab:three}. Note that for simplicity
        we have assumed that each link has the same number (two) of capacity expansion alternatives.



The idea is to determine a set of capacity expansion decisions, minimizing the
total cost of expansion plan while satisfying all the demands under scenarios
\textit{s0} and \textit{s1}. Any feasible solution to this problem requires finding
 a set of flows on the network paths specified in Table \ref{tab:one}.
  These flows should be feasible with respect to not exceeding the installed 
  links capacities and meeting the demands. Let $x_{1,i}, x_{2,i}, x_{3,i}$ and
   $x_{4,i}$ represent the flows passing through paths 1 to 4 under scenario $s_{i}$.
    A feasible solution to the survivable network capacity expansion requires that:
     $  x_{1,0} \geq 4, \hspace{2mm}x_{1,1} \geq 2, \hspace{2mm}x_{2,0}+ x_{3,0}+ x_{4,0} \geq 3 , \hspace{2mm}x_{2,1}+ x_{3,1}+ x_{4,1} \geq 4.5 $ 
     for the network to be able to meet the demands under both scenarios.



%

\begin{table}

\caption{Introductory Example : Demands}

\label{tab:one}

\begin{center}

\begin{tabular}{lccc}

\toprule

Demand & Scenario $s_{0}$ & Scenario $s_{1}$ & Paths\\

\midrule

$d_{1}$ \textit{(a-b)} &4 & 2 & \textit{$p_{1}=(e_{1})$}\\

$d_{2}$ \textit{(c-d)} & 3 & 4.5 & \textit{$p_{2}=(e_{3}), p_{3}=(e_{5},e_{1},e_{2}), p_{4}=(e_{4},e_{2})$}\\

\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}

%

\begin{table}

\caption{Introductory Example : Link Capacities}

\label{tab:two}

\begin{center}

\begin{tabular}{lccl}

\toprule

Link & Scenario $s_{0}$ & Scenario $s_{1}$ \\

\midrule

\textit{$e_{1}$} &4 & 1 \\

\textit{$e_{2}$} & 3 & 3 \\

\textit{$e_{3}$} &2 & 1 \\

\textit{$e_{4}$} & 5 & 4 \\

\textit{$e_{5}$} & 2 & 2 \\

\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}



%

\begin{table}

\caption{Introductory Example : Capacity Expansion Alternatives}

\label{tab:three}

\begin{center}

\begin{tabular}{ccccc}

\toprule

&\multicolumn{2}{c}{Alternative1}&  \multicolumn{2}{c}{Alternative2} \\
Link Data&Capacity& Cost&Capacity&Cost\\

\midrule

\textit{$e_{1}$} &1 & 10 &5 & 15\\

\textit{$e_{2}$} & 3 & 8 &1 & 9\\

\textit{$e_{3}$} &2 & 7 &2 & 5\\

\textit{$e_{4}$} & 5 & 17 &2 & 8\\

\textit{$e_{5}$} & 2 & 3 &1 & 2\\

\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}








\subsection{Modeling Assumptions}



As discussed in the previous section, we are concerned with a set of non-simultaneous failure scenarios 
 $ s\in S$. Each failure scenario corresponds to the failure (partial or complete)
  of a combination of links and/or fluctuation in a combination of node-to-node demands. 
  Therefore we do not assume that only one link can fail at a time, although this is a common
   practice in some of the previous works including
    \cite{Liu:2009:TSP:1460926.1461006,Singh:2009:DDS:1640183.1640202}. 
    Let the random variable representing the occurrence of failure scenarios be
      $\xi$, a single failure scenario be $s$ and demand between a single origin-destination pair be $d$.
       The set of possible failure scenarios, the set of links and the set of demands between origin-destination
        pairs are represented by $S$, $E$ and $D$ , respectively. The following are some key assumptions:


\begin{spacing}{1.5}
\paragraph{Assumption 1}
\textit{ The set of realizations of the random variable $\xi$ is finite. i.e.,
it has a predetermined number of possible values $\xi \in\left\{\xi^1,\xi^2,...,\xi^{|S|}\right\}$. 
The possible realizations of $\xi$ correspond to the occurrence of failure scenarios $s_{1},s_{2},...,s_{|S|}$ 
respectively.}


\paragraph{Assumption 2}
\textit{Associated with each failure scenario $s$ there is an array of links availability coefficients
 $\lambda_{s}=(\lambda_{1,s},\lambda_{2,s},...,\lambda_{|E|,s})$ with $0 \leq \lambda_{e,s}
  \leq 1$ for all $ e\in E. $ Each $ \lambda_{e,s}$ determines a fraction of capacity of link e 
  that is available under failure scenario $s$. 
   Let the initial plus the expanded capacity of link $e$ under the normal conditions be $ U_{e,0}+U_{e,i}$ ; 
   based on this assumption, the available capacity of link $e$ under 
    $s$ would be $ \lambda_{e,s}* (U_{e,0}+U_{e,i})$ .}\\
Based on the assumption 2, for the introductory example problem we have
 $\lambda_{1}=(0.25,1,0.5,0.8,1)$.

\paragraph{Assumption 3}
\textit{Associated with each failure scenario $s$ there is an array of demands coefficients
 $\mu_{i,j,s}=$ for all $i$ and $j$
    $\in V$ with $ \mu_{i,j,s} \ge 0$. Each $ \mu_{i,j,s}$ 
 determines an amount by which the value of demand $d_{i,j}$ varies from its
 value under the normal conditions due to the occurrence of $s$. Let the value
 of demand $d_{i,j}$ under normal condition and under $s$ be $d_{i,j,0}$ and
 $d_{i,j,s}$, respectively; based on this assumption,
 $d_{i,j,s}=\mu_{i,j,s}*d_{i,j,0}$. Note that as $ \mu_{i,j,s} \leq 1$ does not
 necessarily hold, any of the point-to-point demands might decrease or increase based on each scenario.   }\\
Based on the assumption 3, 
for the introductory example problem we have $\mu_{1}=(0.5,1.5)$.\\

\end {spacing}


%To distinguish the normal condition, i.e., the configuration that would apply given no failures, we use the notation of $ s_{0}$. Based on the above assumptions $\lambda_{e,0}=1$   for all $ e \in E $ and $\mu_{d,0}=1$  for all $d \in D $.%
 

\section{Model Formulation}

In this section we propose a two-stage integer programming model for our survivable network capacity expansion problem. We define the following notations:\\\\
\textbf{Indices}\\
$ e \in E$ : Links in the network\\
%$ d \in D$ : Origin-Destination demands\\
$ p \in P_{i,j}$ : Candidate paths between $i$ and $j$\\
$ s \in S$ : Failure scenarios\\$ l\in L_{e}$: Capacity expansion alternatives for link $e$\\\\
\textbf{Data and Parameters}\\
$ k_{e,p_{i,j}}$ : Binary constant, 1 if link $e$ belongs to path $p$ between
$i$ and $j$ ; 0 otherwise\\ 
$ d_{i,j,0}$ : Value of demand $ d_{i,j}$ under normal condition\\ 
$U_{e,0}$ :
Capacity of link $e$ under normal condition\\ $ U_{e,l}$ : 
Additional capacity on link $ e$ if capacity expansion alternative $ l$ is installed\\$ C_{e,l}$ : Cost of expanding the capacity of link $ e$ using alternative $ l$\\ $\lambda_{e,s}$ : Portion of the capacity of link $ e$ available under $ s$\\ $ \mu_{d,s}$ : Coefficient of demand variation$ d$ under $s$\\\\
\textbf{Decision Variables}\\
$ z_{e,l}$ : Binary variable, 1 if alternative $l $ is chosen to be installed on link $e $ ; 0 otherwide\\ 
$ x_{p_{i,j},s}$ : Flow passing through path $p $ for meeting the demand
between $i$ and $j$ under $s $\\\\
\textbf{Formulation of Survivable Network Capacity Expansion (SNCE-1)}\\\\




\begin{equation}
  Min \sum_{e\in E}\sum_{l\in L_{e}}C_{e,l} \hspace{1mm}z_{e,l}
  \label{eq:hist85}
\end{equation}

\hspace{15mm} \textit{subject to.}
 \begin{center}
 \begin{equation}
 \sum_{l\in l_{e}} z_{e,l} \leq 1 \hspace{10mm} \forall e=1,2,...,|E|  \label{eq:hist2}
\end{equation}
\begin{equation}
 \lambda_{e,s}\left(U_{e,0}+\sum_{l\in L_{e}}U_{e,l}z_{e,l}\right)-\sum_{i,j\in
 V}\sum_{p\in P_{i,j}}k_{e,p}x_{p,s}\geq 0 \hspace{5mm} \forall
 e=1,2,...,|E|
 \hspace{2mm} \forall s=0,1,2,...,|S|  \label{eq:hist3}
\end{equation}
\begin{equation}
\sum_{p\in P_{i,j}}x_{p,s}-\mu_{i,j,s}d_{i,j,0}\geq 0 \hspace{5mm} \forall i,j
\in V
\hspace{2mm} \forall s=0,1,2,...,|S| \label{eq:hist4}
\end{equation}
\begin{equation}
 z_{e,l}\in \left\{0,1\right\}\hspace{5mm} \forall e=1,2,...,|E| \hspace{2mm} \forall l=1,2,...,|L_{e}|  \label{eq:hist5}
\end{equation}
\begin{equation}
 x_{p,s}\geq 0 \hspace{5mm} \forall p=1,2,...,|P_{i,j}| \hspace{3mm} (\forall
 i,j \in V), \hspace{2mm}
 \hspace{2mm} \forall s=0,1,2,...,|S| \label{eq:hist6}
\end{equation}
\end{center}
\begin{spacing}{2.5}
\end {spacing}
The objective function in 2.1 simply minimizes the sum of capacity expansion
investments. It only includes the first stage decision variables, implying that
the second stage cost is zero. Constraints in 2.2 restricts the choice of
capacity expansion to no more that one for each link.
%The meaning of the first set of constraints i.e., constraints in \ref{eq:hist2}
% is that for each link in the network one capacity expansion alternative can be chosen.
%This assumption is imposed by the fact that it is normally uneconomical to increase the capacity of a link more than once during the decision making process.%
 The term $\lambda_{e,s}\left(U_{e,0}+\sum_{l\in L}U_{e,l}z_{e,l}\right)$ represents
  the available capacity (including the initial and additional) of link $e$ under $s$
   , and the term $ \sum_{i,j\in
 V}\sum_{p\in P_{i,j}}k_{e,p}x_{p,s}$ is equal to 
   the total amount of flow passing through link $e$. Therefore, constraint set 2.3
    states that the total amount of flow passing through each link should not exceed 
    its available capacity under any of the failure scenarios. Constraint set 2.4
     ensures that all the specified node to node demands are met under all the failure 
     scenarios. In other words, it ensures the survivability of the network.


%\subsection{Introductory Example Re-visited}
\subsection{Illustration of the model formulation for the example network}
Here, we re-visit our introductory example and formally model the problem using the modeling approach and notations introduced above. Based on the data provided for the example in tables \ref{tab:one} to \ref{tab:three}, the capacity expansion problem for the network to be survivable would be as follows:\\

%\textbf{(SNCE-2)}
\begin{eqnarray}
Min  & \hspace{2mm} & 10 z_{1,1}+15 z_{1,2}+8 z_{2,1}+9 z_{2,2}+7 z_{3,1}\\ \nonumber
& \hspace{2mm} & + 5 z_{3,2}+ 17 z_{4,1}+ 8 z_{4,2}+ 3 z_{5,1}+ 2 z_{5,2}\label{eq:hist7}
\end{eqnarray}
\begin{spacing}{1}
\hspace{15mm} \textit{subject to.}
\end{spacing}
\begin{spacing}{1}

\begin{equation}
z_{1,1}+z_{1,2} \leq 1 \label{eq:hist-1}
\end{equation}
\begin{equation}
z_{2,1}+z_{2,2} \leq 1 \label{eq:hist-2}
\end{equation}
\begin{equation}
 z_{2,1}+z_{2,2} \leq 1 \label{eq:hist-3}
\end{equation}
\begin{equation}
 z_{3,1}+z_{3,2} \leq 1 \label{eq:hist-4}
\end{equation}
\begin{equation}
 z_{4,1}+z_{4,2} \leq 1 \label{eq:hist-5}
\end{equation}
\begin{equation}
 z_{5,1}+z_{5,2} \leq 1 \label{eq:hist-6}
 \end{equation}
\begin{equation}
 4+z_{1,1}+5z_{1,2}-(x_{1,1,0}+x_{2,2,0}) \geq 0 \label{eq:hist-7}
\end{equation}
\begin{equation}
 3+3z_{2,1}+z_{2,2}-(x_{2,2,0}+x_{3,2,0}) \geq 0 \label{eq:hist-8}
\end{equation}
\begin{equation}
 2+2z_{3,1}+2z_{3,2}-x_{1,2,0} \geq 0 \label{eq:hist-9}
\end{equation}
\begin{equation}
 5+5z_{4,1}+2z_{4,2}-x_{3,2,0} \geq 0 \label{eq:hist-10}
\end{equation}
\begin{equation}
 2+2z_{5,1}+z_{5,2}-x_{2,2,0} \geq 0 \label{eq:hist-11}
\end{equation}
\begin{equation}
0.25(4+z_{1,1}+5z_{1,2})-(x_{1,1,1}+x_{2,2,1}) \geq 0 \label{eq:hist-12}
\end{equation}
\begin{equation}
3+3z_{2,1}+z_{2,2}-(x_{2,2,1}+x_{3,2,1}) \geq 0 \label{eq:hist-13}
\end{equation}
\begin{equation}
0.5(2+2z_{3,1}+2z_{3,2})-x_{1,2,1} \geq 0 \label{eq:hist-14}
\end{equation}
\begin{equation}
0.8(5+5z_{4,1}+2z_{4,2})-x_{3,2,1} \geq 0 \label{eq:hist-15}
\end{equation}
\begin{equation}
2+2z_{5,1}+z_{5,2}-x_{2,2,1} \geq 0 \label{eq:hist-16}
\end{equation}
\begin{equation}
x_{1,1,0}-4 \geq 0 \label{eq:hist-17}
\end{equation}
\begin{equation}
x_{1,2,0}+x_{2,2,0}+x_{3,2,0}-3 \geq 0  \label{eq:hist-18}
\end{equation}
\begin{equation}
x_{1,1,1}-2 \geq 0 \label{eq:hist-19}
\end{equation}
\begin{equation}
x_{1,2,1}+x_{2,2,1}+x_{3,2,1}-4.5 \geq 0 \label{eq:hist-20}
\end{equation}
\begin{equation}
z_{i,j}\in \left\{0,1\right\} \hspace {2mm} i=1,2,..,5; \hspace {2mm} j = 1,2 \label{eq:hist-21}
\end{equation}
\begin{equation}
x_{1,1,k}, x_{1,2,k} , x_{2,2,k} , x_{3,2,k} \geq 0  \hspace {2mm}  k=1,2 \label{eq:hist-22}
\end{equation}
\end{spacing}

\begin{spacing}{2.5}
\end {spacing}

% In the above formulation equations \ref{eq:hist-1} to \ref{eq:hist-6} say that at most one alternative can be chosen for each link. Equations \ref{eq:hist-7} to \ref{eq:hist-11} represent the links capacity constraints under scenario $ s_{0}$ and equations \ref{eq:hist-12} to \ref{eq:hist-16} are the links capacity constraints under scenario $ s_{1}$. Equations \ref{eq:hist-17} and \ref{eq:hist-18} say that demand 1 and demand 2 should be met under $ s_{0}$ respectively and \ref{eq:hist-19} and \ref{eq:hist-20} say the same thing under $ s_{1}$. Equations \ref{eq:hist-21} and \ref{eq:hist-22} are variables bounds.


To better illustrate how the problem has a two-stage structure here we separate the problems representing each one of the stages :
%\paragraph{First Stage Problem (SNCE-2:1)}

\begin{eqnarray*}
Min  & \hspace{2mm} & 10 z_{1,1}+15 z_{1,2}+8 z_{2,1}+9 z_{2,2}+7 z_{3,1}\\ \nonumber
& \hspace{2mm} & + 5 z_{3,2}+ 17 z_{4,1}+ 8 z_{4,2}+ 3 z_{5,1}+ 2 z_{5,2}
\end{eqnarray*}
\begin{spacing}{1}
\hspace{15mm} \textit{subject to.}
\begin{equation}
z_{1,1}+z_{1,2} \leq 1 \nonumber
\end{equation}
\begin{equation}
z_{2,1}+z_{2,2} \leq 1 \nonumber
\end{equation}
\begin{equation}
 z_{2,1}+z_{2,2} \leq 1 \nonumber
\end{equation}
\begin{equation}
 z_{3,1}+z_{3,2} \leq 1 \nonumber
\end{equation}
\begin{equation}
 z_{4,1}+z_{4,2} \leq 1 \nonumber
\end{equation}
\begin{equation}
z_{i,j}\in \left\{0,1\right\} \hspace {2mm} i=1,2,..,5;  \hspace {2mm} j = 1,2 \nonumber
\end{equation}
\end{spacing}
Note that this problem only contains the first stage ($z$)variables. This problem is a pure integer programming model. Now suppose that a solution to this problem is $\bar{z}$, then the second stage problem will be :
%\paragraph{Second Stage Problem (SNCE-2:2)}
\begin{eqnarray*}
Min \hspace{5mm} 0
\end{eqnarray*}
\begin{spacing}{1}
\hspace{15mm} \textit{subject to.}
\begin{equation}
 4+\bar{z}_{1,1}+3\bar{z}_{1,2}-(x_{1,1,0}+x_{2,2,0}) \geq 0 \nonumber
\end{equation}
\begin{equation}
 3+3\bar{z}_{2,1}+\bar{z}_{2,2}-(x_{2,2,0}+x_{3,2,0}) \geq 0 \nonumber
\end{equation}
\begin{equation}
 2+2\bar{z}_{3,1}+2\bar{z}_{3,2}-x_{1,2,0} \geq 0 \nonumber
\end{equation}
\begin{equation}
 5+5\bar{z}_{4,1}+2\bar{z}_{4,2}-x_{3,2,0} \geq 0 \nonumber
\end{equation}
\begin{equation}
 2+2\bar{z}_{5,1}+\bar{z}_{5,2}-x_{2,2,0} \geq 0 \nonumber
\end{equation}
\begin{equation}
0.25(4+\bar{z}_{1,1}+3\bar{z}_{1,1})-(x_{1,1,1}+x_{2,2,1}) \geq 0 \nonumber
\end{equation}
\begin{equation}
3+3\bar{z}_{2,1}+\bar{z}_{2,2}-(x_{2,2,1}+x_{3,2,1}) \geq 0 \nonumber
\end{equation}
\begin{equation}
0.5(2+2\bar{z}_{3,1}+2\bar{z}_{3,2})-x_{1,2,1} \geq 0 \nonumber
\end{equation}
\begin{equation}
0.8(5+5\bar{z}_{4,1}+2\bar{z}_{4,2})-x_{3,2,1} \geq 0 \nonumber
\end{equation}
\begin{equation}
2+2\bar{z}_{5,1}+\bar{z}_{5,2}-x_{2,2,1} \geq 0 \nonumber
\end{equation}
\begin{equation}
x_{1,1,0}-4 \geq 0  \nonumber
\end{equation}
\begin{equation}
x_{1,2,0}+x_{2,2,0}+x_{3,2,0}-3 \geq 0  \nonumber
\end{equation}
\begin{equation}
x_{1,1,1}-2 \geq 0 \nonumber
\end{equation}
\begin{equation}
x_{1,2,1}+x_{2,2,1}+x_{3,2,1}-4.5 \geq 0 \nonumber
\end{equation}
\end{spacing}

As can be seen, the feasible region of the the second stage problem depends on the decision that are made in the first stage. As the only assumed cost is the capacity expansion costs, the objective function of the second stage problem is zero. This makes the problem a pure allocation problem, i.e., the problem only looks for a feasible set of flow variables given the available capacities. This problem is a linear programming model.

The illustrative example  is solved to optimality using SAS/OR 12.1 on a Core 2 Duo desktop computer with a 3 GHz processor and 4 GB of RAM. The optimal solution to the problem is :\\ $( z_{1,1}, z_{1,2}, z_{2,1}, z_{2,2}, z_{3,1}, z_{3,2}, z_{4,1}, z_{4,2}, z_{5,1}, z_{5,2})=(0, 1, 1, 0, 0, 1, 0, 1, 0, 0)$ and\\  $( x_{1,1,0}, x_{1,2,0}, x_{2,2,0}, x_{3,2,0}, x_{1,1,1}, x_{1,2,1}, x_{2,2,1}, x_{3,2,1})=(4, 2, 4, 2, 0, 0.25, 0, 5.6 )$  with an optimal cost of 36.


\subsection{Scaling and Computational Complications}

As expected and is observed in the formulation of the introductory example, the number of variables and constraints in the model grows rapidly as the network size grows. Even for such a small instance with five links, two point-to-point demands and one failure scenario, the problem has 18 variables (out of which 10 are binary) and 19 constraints. The problem dimension scales fast specifically due to the increase in the number of links.
 %thus an increase in the number of links leads to exponential growth in the number of potential failure scenario, number of paths and number of potential origin-destination pairs with specified demands. 
 
While small sized networks can be directly solved to optimality with mixed integer linear programming solvers; solvers may fail to converge to optimality for middle-sized and large networks. The scaling issue is specially more problematic due to having first stage binary decision variables. In the next chapter, we introduce methods that allow us to solve larger instances of the problem while maintaining the optimality of the solutions.

%\cite{columnGenerationSurvivable}\cite{two-stage transportation}









